package com.wfm.niuke;

import org.junit.Test;

/**
 * [岛屿数量]
 * 主要要写出dfs表格的基础框架
 * 在dfs中，需要判断异常情况：超出边界、不是岛屿
 * 判断后首要的就是更改访问转态，再上下左右遍历
 */
public class NumIslands200 {
    public int numIslands(char[][] grid) {
        int cnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]=='1'){
                    dfs(grid,i,j);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    void dfs(char[][] grid,int i ,int j){
        if(!inArea(grid, i , j)){
            return;
        }
        if(grid[i][j]!='1'){
            return;
        }
        grid[i][j]='2';
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }

    private boolean inArea(char[][] grid, int i, int j) {
        if(i<0||i>=grid.length||j<0||j>=grid[0].length) return false;
        else return true;
    }

    @Test
    public void test200(){
        System.out.println(numIslands(new char[][]{
                {'1','1','1','1','0'},
                {'1','1','0','1','0'},
                {'1','1','0','0','0'},
                {'0','0','0','0','0'}
        }));
    }
}
